package Ep06_BinaryTree.BT19_0654;

import Ep06_BinaryTree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/6/1 12:39
 * 说明：lc 0654
 *
 * 题目：
 *      给定一个不重复的整数数组 nums 。最大二叉树可以用下面的算法从 nums 递归地构建:
 *
 *      创建一个根节点，其值为 nums 中的最大值。
 *      递归地在最大值左边的子数组前缀上构建左子树。
 *      递归地在最大值 右边 的子数组后缀上构建右子树。
 *      返回 nums 构建的 最大二叉树 。
 *
 * 示例：
 *      输入：nums = [3,2,1,6,0,5]
 *      输出：[6,3,5,null,2,0,null,null,1]
 *      解释：递归调用如下所示：
 *      - [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
 *          - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
 *              - 空数组，无子节点。
 *              - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
 *                  - 空数组，无子节点。
 *                  - 只有一个元素，所以子节点是一个值为 1 的节点。
 *          - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
 *              - 只有一个元素，所以子节点是一个值为 0 的节点。
 *              - 空数组，无子节点。
 *
 */

public class Mine {
    private static Map<Integer, Integer> map;       // 储存所有元素的index
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        TreeNode root = traversal(nums, 0, nums.length);

        return root;
    }

    // 递归方法
    private TreeNode traversal (int[] nums, int begin, int end) {
        if (begin >= end)  return null;
        if (end - begin == 1) return new TreeNode(nums[begin]);
        // 获得最大值作为root的值
        int rootVal = 0;
        for (int i = begin; i < end; i++) {
            rootVal = Math.max(rootVal, nums[i]);
        }
        // 获得root的index，以便于后续的分割
        int rootIndex = map.get(rootVal);
        // 创建root
        TreeNode root = new TreeNode(rootVal);

        // 递归构建左子树
        root.left = traversal(nums, begin, rootIndex);
        // 递归构建右子树
        root.right = traversal(nums, rootIndex + 1, end);

        return root;
    }
}
